package com.example.javabasic.suanfa.剑指offer.二维数组查找;

/**
 * @description 二维数组中的查找
 *
 * 核心思想:  二分查找法
 *
 * @Author Lin FuYuan
 * @date 2021/7/2
 */
public class Solution {


    public static void main(String[] args) {
        int[][] arr = {{1,1}};
        find2(2 ,arr);
    }



    public static boolean find(int target, int [][] array) {
        for (int[] ints : array) {
            if(ints.length == 0){
                return false;
            }
            int min = 0;
            int max = ints.length-1;
            if(ints[min]>target){
                continue;
            }
            if(ints[max]<target){
                continue;
            }
            while(min<=max){
                int now = (min+max)/2;
                if(ints[now] == target){
                    return true;
                }else if(ints[now]>target){
                    max = now -1;
                }else if(ints[now]< target){
                    min = now +1;
                }
            }
        }
        return false;
    }




    /**
     * 二维有序数组查找值
     * @author Lin FuYuan
     * @param target
     * @param array
     * @date 2021/7/2
     * @return boolean
     */
    public static boolean find2(int target, int [][] array) {
        //横坐标
        int heng  = 0;
        //纵坐标
        int shu = array[0].length-1;
        while(heng<array.length && shu>=0){
            if(array[heng][shu] == target){
                return true;
            }else if(array[heng][shu]> target){
                shu --;
            }else if(array[heng][shu]< target){
                heng++;
            }
        }
        return false;

    }

}
